package com.lishem.carl._06stackandqueue;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * https://leetcode.cn/problems/top-k-frequent-elements/description/
 * <p>
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * <p>
 * 输出: [1,2]
 * <p>
 * 示例 2:
 * <p>
 * 输入: nums = [1], k = 1
 * <p>
 * 输出: [1]
 */
public class _7LetCode347_前K个高频元素 {


    public static class Pair {
        public int num;
        public int count;

        public Pair(int num, int count) {
            this.num = num;
            this.count = count;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            countMap.put(nums[i], countMap.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<Pair> pq = new PriorityQueue<>((p1, p2) -> p2.count - p1.count);
        for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
            pq.add(new Pair(entry.getKey(), entry.getValue()));
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = pq.poll().num;
        }
        return res;
    }

    public static void main(String[] args) {
        _7LetCode347_前K个高频元素 sol = new _7LetCode347_前K个高频元素();
        System.out.println(Arrays.toString(sol.topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2)));
        System.out.println(Arrays.toString(sol.topKFrequent(new int[]{1}, 1)));
    }
}
